Network Address Translation (NAT) involves translating between Internet Protocol (IP) address spaces in a communication network so as to overcome a deficit of IP addresses for other devices connected to the network, provide anonymity, filter content, monitor network performance and/or share connectivity with the other devices in the network. Unauthorized NAT devices or NAT software in the network represent a significant network security threat because they may provide unrestricted access to the other network-connected devices or data. Wireless NATs (e.g., Wi-Fi® NAT devices) pose a particular security risk because they may allow unauthorized access to the network from considerable distances without wired connections. It is also important for network behavior analysis systems to be able to detect NAT devices. Accordingly, detecting and distinguishing between unauthorized and authorized NAT devices and NAT software is important for purposes of network security and behavior analysis.